import typing
from provate import listNode,list2pList,print_List_node


# 题目：输入两个递增排序的链表，合并这两个链表使得新链表中的节点仍然是递增排序的


def merge_list_node(head1:listNode, head2:listNode) -> listNode:
    if not head1:
        return head2
    if not head2:
        return head1

    merge_head = None

    if head1.value<head2.value:
        merge_head = head1
        merge_head.next = merge_list_node(head1.next, head2)

    else:
        merge_head = head2
        merge_head.next = merge_list_node(head1, head2.next)

    return merge_head

if __name__ == '__main__':
    l1 = [1,2,3,4,8,9]
    l2 = [2,4,5,7,9,10]
    head1 = list2pList(l1)
    head2 = list2pList(l2)
    merge = merge_list_node(head1, head2)
    print_List_node(merge)